// 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。
// 给定的字符串只含有小写英文字母，并且长度不超过10000。

// 暴露接口
function repeatedSubstringPattern(s: string): boolean {
  let maxIndex: number = Math.floor(s.length / 2) + 1; // 计算对半最大索引
  for (let i = 1; i <= maxIndex; i++) {
    let currStr: string = s.substring(0, i); // 切分出子串
    if (checkSinglePattern(s, currStr)) {
      return true;
    }
  }
  return false;
}

// 检查子字符串是否能拼出一个完整的字符串
function checkSinglePattern(s: string, splitS: string): boolean {
  let count: number = Math.floor(s.length / splitS.length); // 检测能被拼几次
  if (s.length % splitS.length !== 0 || count < 2) {
    // 如果凑不整直接返回false
    return false;
  }
  let str: string = ""; // 当前拼接出的字符串
  for (let i = 0; i < count; i++) {
    str = str + splitS;
  }
  return str === s; // 判断拼接结果是否匹配
}

// 这道题目使用的是直接思路是基于一个枚举法来进行求解
// 如果一个长度为 n 的字符串 s 可以由它的一个子串重复多次构成，那么:
// 1. 子串长度一定是原串的倍数
// 2. 子串至少需要重复一次，所以子串长度不会大于原字符串长度的一半
// 基于这两点我们就可以写出代码。
// 当然，这道题目的最优解法是使用了KMP算法，但这个手写起来确实比较有难度。
